package 常见算法.分治之快速排序;

import java.util.Random;

/**
 * @Date 2024/6/22 20:43
 * @description: 库存管理: 找到最小的几个数 (建大跟堆)
 * .            https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/description/
 * @Author LittleNight
 */
public class likou159 {
    // top k 问题
    public int[] inventoryManagement(int[] nums, int k) {
        // 1. 直接排序, 然后取k个元素
        // 2. 堆排序, 找最小的k, 建一个大跟堆 O(NlogK)
        // 3. 快速选择排序 (分治的思想) 这也就是 TopK 问题 O(N)
        // 把最小的元素丢到数组的前面了, 注意不是完全按照从小到大进行排序的
        qsort(nums, 0, nums.length - 1, k);
        // 这里就是已经排好序了, 前面的k个就是最小的
        int[] ret = new int[k];
        for(int i = 0; i < k; i++)
            ret[i] = nums[i];
        return ret;
    }
    public void qsort(int[] nums, int l, int r, int k) {
        // 递归终止条件, 区间不存在,或者只有一个元素, 就不用在排序了
        if(l >= r) return;

        // 1. 随机选择一个基准元素 + 数组分三块
        // new Random.().nextInt(10) 0~10 的一个随机数, [0,n) 边界条件查一下
        int key = nums[new Random().nextInt(r - l + 1) + l];

        int left = l - 1, right = r + 1, i = l;

        // 快排核心代码, 可以记住
        while(i < right) {
            // if(nums[i] < k) swap(nums, ++left, i++);
            if(nums[i] < key) swap(nums, ++left, i++);
            else if(nums[i] == key) i++;
            else swap(nums, --right, i);
        }

        // 区间长度判断. 这个和 找第k大的元素很类似：
        // https://leetcode.cn/problems/kth-largest-element-in-an-array/description/
        // 区别就是这里没有返回值。最大值是判断右边, 找第几小值是判断左边
        // 【l, left】[left + 1, right - 1] 【right, r】
        int a = left - l + 1, b = (right - 1) - (left + 1) + 1;
        if(a > k)  qsort(nums, l, left, k); // 在最左边区间, 直接递归去找
        else if(a + b >= k) return; // 说明在 a + b 区间内, 由于 b 区间内都相同, 所以不必排序
        else  qsort(nums, right, r, k - a - b); // 在 a + b + c 区间内, 右边的得在进行拍一下
    }
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
